/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/letter-combinations-of-a-phone-number
   @Language: C++
   @Datetime: 19-05-29 11:25
   */

class Solution {
	void backtrack(const string dict[], string &digits, int pos, string &s, vector<string> &vs){
		if(pos==digits.length()){
			vs.push_back(s);
			return;
		}
		for(const char &c:dict[digits[pos]-'0']){
			s.push_back(c);
			backtrack(dict,digits,pos+1,s,vs);
			s.pop_back();
		}
	}
public:
	vector<string> letterCombinations(string digits) {
		const string dict[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
		vector<string> vs;
		string s;
		if(digits.length()==0) return vs;
		backtrack(dict,digits,0,s,vs);
		return vs;
	}
};
